A Near Video-on-Demand (NVOD) system, which has become increasingly popular, typically broadcasts media data using a cyclic re-broadcast technique which refers to a repetitive broadcast on multiple channels in a cyclic manner having a fixed time interval between channels. In other words, a Near Video-on-Demand system is capable of continuously broadcasting the same movie on several channels at a given interval. Since this system can utilize both the mechanisms of broadcasting and multicasting, the requirement on the network bandwidth is significantly reduced. Furthermore, since there is a fixed interval length between channels during broadcasting, a user can choose where to start the movie by selecting one of the several channels. Also, by shifting between channels, the user can achieve the effect of fast forward or rewind. For instance, a movie with a length of 120 minutes may be broadcast continuously and cyclically on 12 channels, such that there is a ten-minute interval between broadcasting on each channel. If the first channel broadcasts at 12:00 am, the second channel will broadcast at 12:10 am, and so on.
As an example, if a movie is 24 seconds in length, and is being broadcast continuously and cyclically on channels 1, 2, 3, and 4, then there is an interval of 6 seconds between broadcast on each channel. One second of the movie is defined as a block, so that a movie with 24 seconds has 24 blocks in total. Accordingly, the broadcast time differential between the channels is 6 blocks. For purpose of illustration, the blocks are numbered from 0 to 23. As shown in FIG. 1, when channel 1 needs block 0, then block 6, block 12 and block 18 are fed to channel 2, channel 3, and channel 4, respectively.
The following will discuss three popular conventional data placement methods, using the example cited hereinabove, which are: continuous data placement, region-based data to placement, and region-based data placement with block grouping.
FIG. 2 illustrates the access order of the above-mentioned 24 second movie when storing data using the first listed prior art method, continuous data placement. The continuous data placement method refers to the method whereby data is placed continuously in some order so that when channel 1 finishes accessing block 0, the read/write head has to search for block 6 for channel 2, and so on. According to this method, the read/write head must search for the next block every time it finishes accessing a given block, causing a significant time delay required for searching. When this method is applied to a system having continuous and cyclic re-broadcasting capability, a considerable search time is necessary because of the fact that the read/write head has to continuously access the blocks that are located in different sections of the file.
FIG. 3 illustrates the access order of the above-mentioned 24-second movie when storing data according to the second listed prior art method, region-based data placement. The region-based data placement method divides the direct access device into a number of regions and places the divided data into these regions. Because of the nature of the cyclic re-broadcast technique, the data to be broadcast for each channel may be arranged to be placed in a single region. For example, when channel 1 completes accessing the data of block 0, the read/write head can access the data of block 6 for channel 2 in the same region. With the broadcast data regionalized, the search time of the direct access device will be shortened, as will the physical distance since data blocks, which are cyclicly read, are stored in the same physical region. However, when the read/write head moves from one region to another, it is still necessary for the direct access device to search.
FIG. 4 illustrates the access order of the above-mentioned 24 second movie when storing data according to the third listed prior art method, region-based data placement with block grouping. The so-called region-based data placement with block grouping furthers the region-based data placement method by utilizing a block grouping scheme that places together all blocks that are required by all channels at one time, so that the search time between blocks can be reduced. Thus, when channel 1 finishes accessing block 0, the read/write head does not have to search further but access block 6 immediately for channel 2. However, when the system finishes accessing block 18 for channel 4, the read/write head has to search block 1 for channel 1, etc. Thus, frequent searching remains, which causes detrimental delays in NVOD systems.
In addition to the above-mentioned three methods of data placement, a study has also be conducted of additional related prior art publications; however, these publications do not disclose data storage designs for cyclic and continuous broadcasting of a movie.
For example, P. Venka Rangan and Harrick M. Vin's article entitled "Efficient Storage Techniques for Digital Continuous Multimedia" (IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 4, 1993), proposes a limit on the data placement method to reduce the search time by the magnet head of a storage device and to increase the system efficiency thereby. In addition, Shahram Ghandeharizodeh, Seon Ho Kim and Cyrus Shahabi's article entitled "On Configuring a Single Disk Continuous Media Servers" (SIGMETRICS95, 1995), proposes a similar concept, referred to as the region-based data placement. However, neither of these methods are designed for the data storage for cyclic and continuous broadcasting of a movie. Nor do either disclose optimizing disk search time.
On the other hand, the article by Meng-Hied Lee, Meng Chang Chen, Jan Ming Ho and Ming Tat Ko entitled "On the Disk Layout of Near Video On Demand System" (Proc. Of the 1997 IS&T/SPIE Symp. On Electronic Imaging: Science and Technology, Conference on Storage and Retrieval for Still Image and Video Database) discloses a method that purportively refines the region-based data placement method by placing the data blocks within a region in a continuous position to reduce the search time by the magnetic head. However, this method has not optimized the data placement to avoid unnecessary search by the magnetic head. In addition, this method limits the video data to the same length and applies to the data placement only in a single hard disk. This is different from the present invention whose direct access device can be a magnetic disk or a magnetic disk array. Moreover, the present invention does not pose any limit on the length of a movie and therefore provides greater practicality in actual applications.
Thus, it is an object of the present invention to overcome the deficiencies and short-comings of the prior art.